// 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
// 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

// 输入: `[1, 5, 11, 5]`
// 输出: true
// 解释: 数组可以分割成 `[1, 5, 5]` 和 `[11]`.
// 思路，动态规划
// 可以转换为01背包问题，背包的体积为 sum / 2,背包能够放的最大和等于背包大小的时候，为true
// 1. `dp[j]`,容量为j的背包，能够容纳的最大价值，j为目标和，`dp[j]`是最大和
// 2. 递归公式： `dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])`
// 3. dp初始化 `dp[0] = 0`
// 4. 遍历顺序
// 5. 举例
function canPartition(nums) {
    let sum = nums.reduce((sum, cur) => sum + cur)
    if (sum % 2 === 1) {
        return false
    }
    let target = sum / 2
    let dp = new Array(target + 1).fill(0)
    for (let i = 1; i < nums.length; i++) {
        for (let j = target; j >= nums[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])            
        }        
    }
    return dp[target] === target
}

console.log(canPartition([1, 5, 11, 5]))

function canPartition2(nums) {
    let sum = nums.reduce((sum, cur) => sum + cur)
    if (sum % 2 === 1) {
        return false
    }
    let target = sum / 2
    let dp = new Array(nums.length).fill(0).map(item => new Array(target + 1).fill(0))
    for (let j = 0; j <= target; j++) {
        if (j >= nums[0]) {
            dp[0][j] = nums[0]
        }        
    }
    for (let i = 1; i < nums.length; i++) {
        for (let j = 1; j <= target; j++) {
            if (j < nums[i] ) {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i-1][j-nums[i]] + nums[i])
            }          
        }        
    }
    return dp[nums.length - 1][target] === target
}

console.log(canPartition2([1, 5, 11, 5]))